package stud.solver;

import core.problem.Problem;
import core.solver.algorithm.searcher.AbstractSearcher;
import core.solver.algorithm.heuristic.Predictor;
import core.solver.queue.Frontier;
import core.solver.queue.Node;

import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
import java.util.PriorityQueue;

/**
 * 迭代加深的A*算法，经过性能优化
 */
public class IdAStar extends AbstractSearcher {
    private final Predictor predictor; // 启发式预测器
    private int cutoff;                 // 当前裁剪阈值
    private int newCutoff;              // 下一个迭代的裁剪阈值
    private int maxIteratorDepth = 256; // 最大迭代深度
    private int expandedNodesCount = 0; // 统计扩展的节点数

    public IdAStar(Frontier frontier, Predictor predictor) {
        super(frontier); // Frontier作为堆栈使用
        this.predictor = predictor; // 初始化预测器
    }

    @Override
    public Deque<Node> search(Problem problem) {
        // 首先检查问题是否可解
        if (!problem.solvable()) {
            return null; // 不可解返回null
        }

        Node root = problem.root(predictor); // 获取根节点
        cutoff = root.evaluation(); // 初始化裁剪阈值为根节点的评估值

        // 迭代进行搜索，直到达到最大深度
        while (cutoff < maxIteratorDepth) {
            // 清空 Frontier，并将根节点压入 Frontier 中
            frontier.clear();
            frontier.offer(root);
            newCutoff = Integer.MAX_VALUE; // 初始化为较大值
            expandedNodesCount = 0; // 重置扩展节点计数

            Set<Object> visited = new HashSet<>(); // 记录访问过的节点，避免回溯

            // 使用优先队列按启发式评估值对节点进行排序
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>((a, b) -> Integer.compare(a.evaluation(), b.evaluation()));

            // 深度优先搜索
            while (!frontier.isEmpty()) {
                expandedNodesCount++; // 每扩展一个节点，计数增加
                Node currentNode = frontier.poll(); // 弹出最上面的节点

                // 如果节点已经访问过，跳过
                if (!visited.add(currentNode.getState())) {
                    continue;
                }

                // 检查当前节点是否是目标节点
                if (problem.goal(currentNode.getState())) {
                    return generatePath(currentNode); // 返回找到的路径
                }

                // 获取当前节点的所有子节点
                for (Node childNode : problem.childNodes(currentNode, predictor)) {
                    int childEvaluation = childNode.evaluation(); // 缓存评估值

                    // 判断子节点的评估值是否在裁剪阈值之内
                    if (childEvaluation <= cutoff) {
                        frontier.offer(childNode); // 将子节点添加到Frontier中
                    } else {
                        // 更新新的裁剪阈值
                        newCutoff = Math.min(newCutoff, childEvaluation);
                    }
                }
            }
            cutoff = newCutoff; // 更新裁剪阈值
        }
        return null; // 未找到路径
    }

    @Override
    public long  nodesExpanded() {
        return expandedNodesCount; // 返回扩展的节点数
    }

    @Override
    public long nodesGenerated() {
        return nodesExpanded; // 生成的节点数未实现
    }
}


